package qjc.g_链表;

import com.链表.练习题.ListNode;

public class g12_排序链表 {
    /**
     * 使用快慢指针找到链表的中点，将链表从中间断开，形成两个独立子链表，
     * 合并两个已排序的子链表，并返回合并后的头节点
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        return mergeList(left, right);
    }

    private ListNode mergeList(ListNode left, ListNode right) {
        ListNode sential = new ListNode(0);
        ListNode cur = sential;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        if (left == null) {
            cur.next = right;
        }
        if (right == null) {
            cur.next = left;
        }
        return sential.next;
    }
}
